// 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
// 如果数组中不存在目标值 target，返回 [-1, -1]。

// 要求算法的时间复杂度小于On

// 暴露接口
const searchRange = function (nums: number[], target: number) {
    return [searchRange_leftBound(nums, target), searchRange_rightBound(nums, target)]
};

// 辅助方法，查找左边界
function searchRange_leftBound(nums: number[], target: number): number {
    let left: number = 0;// 左指针
    let right: number = nums.length;// 右指针
    while (left < right) {
        let mid: number = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return nums[right] === target ? right : -1;
};

// 辅助方法，查找右边界
function searchRange_rightBound(nums: number[], target: number) {
    let left: number = 0;
    let right: number = nums.length - 1;
    while (left <= right) {
        let mid: number = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return nums[right] === target ? right : -1;
};

// 这道题是一道非常好的复习二分查找的算法题
// 而在这里需要用对二分搜索进行适当的变形
// 因为需要统计左右区间内的元素个数，所以需要进行二轮二分查找
// 第一轮二分查找负责找到左边间
// 而第二轮二分查找负责找到右边间
// 而找到左右区间的二分查找算法是需要在原逻辑上进行改写
// 这里建议在纸上画一画，重点考虑这几个地方
// 1.循环的终点是否左右指针相等
// 2.既然是找边界，那么如果当前值等于目标值的时候，左右指针怎么变
// 3.二分查找的左右区间实际上就是不断地对比缩小搜索区间，那么这个搜索区间的左右边是开还是闭？
// 4.结尾的返回值要判断，因为并不能保证最后的左右指针适合目标值一样的
// 在纸上画的案例，可以思考当一列数全部相等的时候：例如“5,5,5,5,5,5”这种极端情况，怎么找到左右区间。
